package com.xk._02算法篇._06greedy;

import java.util.Arrays;

/**
 * @description: 零钱兑换
 * @author: xu
 * @date: 2022/10/17 21:03
 */
public class CoinChange {
    public static void main(String[] args) {
        coinChange(new Integer[]{1, 5, 10, 25}, 41);
        coinChange1(new Integer[]{1, 5, 10, 25}, 41);
        coinChange2(new Integer[]{1, 5, 10, 25}, 41);
    }

    static void coinChange2(Integer[] faces, int money){
        // 1 5 20 25
        Arrays.sort(faces); // 升序
        int coins = 0, ids = faces.length - 1;
        while (ids >= 0){
            while (money >= faces[ids]) {
                money -= faces[ids];
                coins++;
                System.out.println(faces[ids]);
            }
            ids--;
        }
        System.out.println(coins);
    }

    static void coinChange1(Integer[] faces, int money){
        Arrays.sort(faces, (Integer f1, Integer f2) -> f2 - f1);//降序
        int coins = 0, i = 0;
        while (i < faces.length) {
            if (money < faces[i]) {
                i++;
                continue;
            }
            System.out.println(faces[i]);
            money -= faces[i];
            coins++;
        }
        System.out.println("共有" + coins + "枚硬币");
    }

    static void coinChange(Integer[] faces, int money){
        Arrays.sort(faces);
        int coins = 0;
        for (int i = faces.length - 1; i >= 0; ) {
            if (money < faces[i]) {
                i--;
                continue;
            }
            System.out.println(faces[i]);
            money -= faces[i];
            coins++;
        }
        System.out.println(coins);
    }
}
